# Сортировка, выбор и поиск

## Сортировка

Поскольку Spire предоставляет специализированный класс типов упорядочения, 
имеет смысл также предоставить свои собственные методы для выполнения операций на основе `Order`. 
Эти методы определены в массивах и "возникают на месте", изменяя массив. 
Другие коллекции могут воспользоваться преимуществами сортировки путем преобразования в массив, 
последующей сортировки и обратного преобразования (что уже делает платформа коллекций Scala в большинстве случаев). 
Таким образом, Spire поддерживает как изменяемые массивы, так и неизменяемые коллекции.

Методы сортировки можно найти в объекте `spire.math.Sorting`. Это:

- `quickSort`: самый быстрый, \\(O(n*log(n))\\), нестабильный с потенциалом \\(O(n^{2})\\) в худшем случае
- `mergeSort`: также быстрый, \\(O(n*log(n))\\), стабильный, но выделяет дополнительное временное пространство
- `insertionSort`: \\(O(n^{2})\\), но стабильный и быстрый для небольших массивов
- `sort`: псевдоним для `quickSort`

Оба `mergeSort` и `quickSort` делегируют `insertionSort` при работе с массивами (или срезами) ниже определенной длины. 
Поэтому правильнее было бы назвать их гибридными сортировками.

## Выборка

Методы выбора можно найти в аналогичном объекте `spire.math.Selection`. 
Учитывая массив и индекс `k`, эти методы помещают _k-й_ наибольший элемент в позицию `k`, 
гарантируя, что все предыдущие элементы меньше или равны, 
а все последующие элементы больше или равны _k-му_ элементу.

Определено два метода:

- `quickSelect`: обычно быстрее, нестабильнее, потенциально плохой в худшем случае
- `linearSelect`: обычно медленнее, но с гарантированной линейной сложностью
- `select`: псевдоним для `quickSelect`

## Поиск

Методы поиска расположены в объекте `spire.math.Searching`. 
Учитывая отсортированный массив (или индексированную последовательность), 
эти методы найдут индекс нужного элемента (или вернут `-1`, если он не найден).

- `search(array, item)`: находит индекс `item` в `array`.
- `search(array, item, lower, upper)`: поиск осуществляется только между `lower` и `upper`.

Поиск также поддерживает более эзотерический метод: `minimalElements`. 
Этот метод возвращает минимальные элементы частично упорядоченного набора.

---

**Ссылки:**

- [Spire home page](https://typelevel.org/spire)
